package com.cqs.leetcode.tree;

import com.cqs.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author lixqw
 * @date 2020/8/18
 */
public class ConvertSortedArraytoBinarySearchTree108 {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null) return null;
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int mid = (right - left) / 2 + left;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }

    public static void main(String[] args) {
        ConvertSortedArraytoBinarySearchTree108 c = new ConvertSortedArraytoBinarySearchTree108();

        List<int[]> tests = new ArrayList<>();
        tests.add(new int[]{-10, -3, 0, 5, 9});
        for (int[] test : tests) {
            System.out.println(c.sortedArrayToBST(test));
        }

    }

}
